package com.zhengb.algorithmdemo.leetcode.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
 * <p>
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回其层次遍历结果：
 * <p>
 * [
 * [3],
 * [9,20],
 * [15,7]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author zhengbo
 * @date 2020/3/16
 */
public class TreeLevelOrder {

    /**
     * 从队列中依次移除所有元素
     *
     * @param queue
     * @return
     */
    private List<TreeNode> pollAllElements(LinkedList<TreeNode> queue) {

        List<TreeNode> nodeList = new ArrayList<>(queue.size());
        while (!queue.isEmpty()) {
            nodeList.add(queue.poll());
        }
        return nodeList;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        //结果存放list
        List<List<Integer>> resultList = new ArrayList<>();

        //创建一个队列
        LinkedList<TreeNode> queue = new LinkedList<>();

        //处理思路：根节点先入队列，然后出队列，出队列后将左右子节点入队列--第一层处理完成
        //第二层节点依次出队列，遍历每个出队列的节点，节点的子节点依次入队列--第二层处理完成

        //根节点先入队列
        queue.add(root);

        while (!queue.isEmpty()) {
            //队列中所有元素出队列
            List<TreeNode> nodeList = pollAllElements(queue);

            //当前层值List
            List<Integer> curLevelValues = new LinkedList<>();
            for (TreeNode node : nodeList) {
                curLevelValues.add(node.val);

                //出队列的节点的左右子节点入队列
                if (node.left != null) {
                    queue.add(node.left);
                }

                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            resultList.add(curLevelValues);
        }
        return resultList;

    }


    public static void main(String[] args) {

        TreeLevelOrder levelOrder = new TreeLevelOrder();

        TreeNode three = new TreeNode(3);
        TreeNode nine = new TreeNode(9);
        TreeNode twenty = new TreeNode(20);
        TreeNode fifteen = new TreeNode(15);
        TreeNode seven = new TreeNode(7);

        three.left = nine;
        three.right = twenty;

        twenty.left = fifteen;
        twenty.right = seven;

        List<List<Integer>> lists = levelOrder.levelOrder(three);

        System.out.println(lists);
    }
}
